package leetcode_81_100;

public class search_81 {
    /**
     * 存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
     * 给你 旋转后 的数组 nums 和一个整数 target
     * 请你编写一个函数来判断给定的目标值是否存在于数组中。
     * 如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
     * 你必须尽可能减少整个操作步骤。
     * @param nums
     * @param target
     * @return
     */
    public boolean search(int[] nums, int target) {
        /**
         * 二分法，已经无法利用头元素实时判断mid左右两边哪边是有序的，因为存在 11101111这种情况
         * 需要去掉重复项，即头部start++
         */
        int left=0,right=nums.length-1,n=nums.length,
                start=0,end=n-1;
        if (n == 1)
            return nums[0] == target;
        while(left<=right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return true;
            if(nums[start] == nums[mid]){
                start++;
                left=start;
            }
            else if (nums[start] < nums[mid]) {     //mid大于数组头元素时，说明左边区间有序，右边区间无序
                if (nums[start] <= target && target < nums[mid]) {       //target大小在其之间，就在左边
                    right = mid - 1;
                } else {                         //否则右边
                    left = mid + 1;
                }
            } else {                         //mid小于数组头元素时，说明左边区间无序，右边区间有序
                if (nums[mid] < target && target <= nums[end]) {   //target大于mid，小于末尾元素，则target就在右区间
                    left = mid + 1;
                } else {                         //否则在左区间
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
